package leetcode;

//给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
//注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class problems_030 {

    public static void main(String[] arge) {
        System.out.println(new Solution().findSubstring("barfoothefoobarman", new String[]{"foo","bar"}));
    }

//    static class Solution {
//        public List<Integer> findSubstring(String s, String[] words) {
//            List<Integer> res = new ArrayList<>();
//            if (s == null || s.length() == 0 || words == null || words.length == 0) return res; // 空值判断
//            int wordLength = words[0].length();
//            int sumLength = wordLength * words.length; // 匹配总长度
//            for (int i = 0; i <= s.length() - sumLength; i++) {
//                String strSub = s.substring(i, i + sumLength); // 子串
//                // 判断子串实付符合
//
//
//                for (int j = 0; j < words.length; j = j + wordLength) {
//                    words[j]
//
//
//
//                    if (strSub.indexOf(words[j]) == -1) break;
//                    markNum++;
//                    strSub = strSub.replaceFirst(words[j], " ");
//                }
//
//            }
//            return res;
//        }
//    }


    static class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> res = new ArrayList<>();
            if (s == null || s.length() == 0 || words == null || words.length == 0) return res;
            HashMap<String, Integer> map = new HashMap<>();
            int one_word = words[0].length();
            int word_num = words.length;
            int all_len = one_word * word_num;
            for (String word : words) {
                map.put(word, map.getOrDefault(word, 0) + 1);
            }
            for (int i = 0; i < s.length() - all_len + 1; i++) {
                String tmp = s.substring(i, i + all_len);
                HashMap<String, Integer> tmp_map = new HashMap<>();
                for (int j = 0; j < all_len; j += one_word) {
                    String w = tmp.substring(j, j + one_word);
                    tmp_map.put(w, tmp_map.getOrDefault(w, 0) + 1);
                }
                if (map.equals(tmp_map)) res.add(i);
            }
            return res;
        }
    }


//    static class Solution {
//        public List<Integer> findSubstring(String s, String[] words) {
//            List<Integer> ret = new ArrayList<>();
//            if(null == s || s.length() == 0 || null == words){}
//            // 初始化
//            int sumLength = 0; // 匹配总长度
//            for (int i = 0; i < words.length; i++) {
//                sumLength += words[i].length();
//            }
//            List<MyObj> listObj = new ArrayList<>();
//            // 遍历
//            for (int i = 0; i <= s.length() - sumLength; i++) {
//                char sChar = s.charAt(i);
//                System.out.println("当前指针：" + i + "，字母：" + sChar);
//                // 追加
//                for (int j = 0; j < words.length; j++) {
//                    if(words[j].charAt(0) == sChar){
//                        listObj.add(new MyObj(j, i, new ArrayList<>()));
//                        System.out.println("--追加对象，开始值：" + words[j]);
//                    }
//                }
//                // 遍历待处理对象
//                for (int j = listObj.size() -1; j >= 0; j--) {
//                    MyObj obj = listObj.get(j);
//                    if(words[obj.getCurWordIndex()].length() >= obj.getMyIndex() + 1){
//                        // 匹配判断
//                        if(sChar != words[obj.getCurWordIndex()].charAt(obj.getMyIndex())){
//                            listObj.remove(obj);
//                            continue;
//                        }
//                        // 字符串匹配
//                        obj.setMyIndex(obj.getMyIndex()+1);
//                    }else {
//                        // 超长，一个word已经判断完
//                        // 标记
//                        obj.getNoArr().add(obj.getCurWordIndex());
//                        if(obj.getNoArr().size() == words.length){
//                            ret.add(obj.getStartIndex());
//                            listObj.remove(obj);
//                            continue;
//                        }
//                        // 判断剩下的实付存在一致
//                        for (int k = 0; k < words.length; k++) {
//                            if(obj.getNoArr().indexOf(k) != -1) continue;
//                            if(words[k].charAt(0) == sChar){
//                                listObj.add(new MyObj(k, i, new ArrayList<Integer>(obj.getNoArr())));
//                                listObj.remove(obj);
//                                System.out.println("--次级对象，开始值：" + words[k]);
//                                continue;
//                            }
//                        }
//                    }
//                }
//            }
//            return ret;
//        }
//    }
//
//    static class MyObj{
//        int startIndex = 0; // 索引开始
//        int myIndex = 0; // 对象索引
//        int curWordIndex = 0; // 当前对象索引
//        List<Integer> noArr = new ArrayList<>(); // 已处理对象
//        public MyObj(int wordIndex,int startIndex, List<Integer> oldArr){
//            setStartIndex(startIndex);
//            setCurWordIndex(wordIndex);
//            setNoArr(oldArr);
//        }
//        public int getMyIndex() {
//            return myIndex;
//        }
//
//        public void setMyIndex(int myIndex) {
//            this.myIndex = myIndex;
//        }
//
//        public int getCurWordIndex() {
//            return curWordIndex;
//        }
//
//        public void setCurWordIndex(int curWordIndex) {
//            this.curWordIndex = curWordIndex;
//        }
//
//        public List<Integer> getNoArr() {
//            return noArr;
//        }
//
//        public void setNoArr(List<Integer> noArr) {
//            this.noArr = noArr;
//        }
//
//        public int getStartIndex() {
//            return startIndex;
//        }
//
//        public void setStartIndex(int startIndex) {
//            this.startIndex = startIndex;
//        }
//    }
}
